package com.dmzc.sort;

public class QuickSort {
    public static void main(String[] args) {
        Node1[] node1s = new Node1[5];
        node1s[0] = new Node1(4, 1);
        node1s[1] = new Node1(5, 2);
        node1s[2] = new Node1(1, 3);
        node1s[3] = new Node1(1, 4);
        node1s[4] = new Node1(3, 5);
        quick_sort(node1s, 0, node1s.length - 1);
        for (int i = 0; i < node1s.length; i++) {
            System.out.println(node1s[i]);
        }
    }

    public static void quick_sort(Node1[] A, int p, int r) {
        if (p >= r) return;
        int q = pivot(A, p, r);
        quick_sort(A, p, q - 1);
        quick_sort(A, q + 1, r);
    }

    private static int pivot(Node1[] A, int p, int r) {
        Node1 pivot = A[r];
        int i = p;
        for (int j = p; j < r; ++j) {
            if (A[j].index < pivot.index) {
                if (i == j) {
                    ++i;
                } else {
                    Node1 tmp = A[i];
                    A[i++] = A[j];
                    A[j] = tmp;
                }
            }
        }
        Node1 tmp = A[i];
        A[i] = A[r];
        A[r] = tmp;
        return i;
    }
}
